package com.LeetCode.Math;

import org.junit.Test;

/**
 * 快速幂 数的整数次方
 */
public class QuickPow {

    public double myPow_recur(double x , int n){
        if(n == 0) return 1;
        double half_pow = myPow_recur(x,n/2);
        return n % 2 == 0 ? half_pow * half_pow : half_pow * half_pow * x;
    }

    public double myPow(double x , int n){
        double res = 1.0;

        double x_contribute = x;

        while(n>0){
            if(n%2 == 1){
                res *= x_contribute;
            }
            x_contribute *= x_contribute;
            n /= 2;
        }
        return res;
    }

    @Test
    public void test(){
        double base = 2.00000;
        int n = 10;
        System.out.println(myPow(base,n));
        System.out.println(myPow_recur(base,n));
    }
}
